home *** CD-ROM | disk | FTP | other *** search
/ CU Amiga Super CD-ROM 19 / CU Amiga Magazine's Super CD-ROM 19 (1998)(EMAP Images)(GB)[!][issue 1998-02].iso / CUCD / Programming / LEDA / source / src / graph / _graph.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-11-16  |  4.7 KB  |  239 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  3.1c
  4. +
  5. +
  6. +  _graph.c
  7. +
  8. +
  9. +  Copyright (c) 1994  by  Max-Planck-Institut fuer Informatik
  10. +  Im Stadtwald, 6600 Saarbruecken, FRG     
  11. +  All rights reserved.
  12. + 
  13. *******************************************************************************/
  14.  
  15.  
  16.  
  17. #include <LEDA/graph.h>
  18.  
  19. // constructors, destructor, operator=, ...
  20.  
  21. graph::graph() 
  22. { max_n_index = -1;
  23.   max_e_index = -1; 
  24.   parent = 0; 
  25.   undirected = false;
  26.  }
  27.  
  28.  
  29. graph& graph::operator=(const graph& G)
  30. { node v,w;
  31.   edge e,e1;
  32.  
  33.   if (&G == this) return *this;
  34.  
  35.   node* node_vec = new node[G.max_n_index+1];
  36.  
  37.   edge* edge_vec = new edge[G.max_e_index+1];
  38.  
  39.   clear();
  40.  
  41.   forall_nodes(v,G) 
  42.     node_vec[v->name] = new_node(v->data[0]);
  43.                              
  44.   forall_edges(e,G) 
  45.    { v = node_vec[e->s->name];
  46.      w = node_vec[e->t->name];
  47.      edge_vec[e->name] = e1 = new edge_struct(v,w,e->data[0]);
  48.      E.append(edge_link(e1));
  49.      e1->name = ++max_e_index;
  50.     }
  51.  
  52.   forall_nodes(v,G) 
  53.   { node v1 = node_vec[v->name];
  54.     forall_out_edges(e,v)
  55.        v1->adj_edges[0].append(adj_link1(edge_vec[e->name]));
  56.     forall_in_edges(e,v)
  57.        v1->adj_edges[1].append(adj_link2(edge_vec[e->name]));
  58.    }
  59.  
  60.   forall_nodes(v,*this) init_adj_iterator(v); 
  61.  
  62.   parent = G.parent;
  63.   undirected = G.undirected;
  64.  
  65.   delete node_vec;
  66.   delete edge_vec;
  67.  
  68.   return *this;
  69. }
  70.  
  71.  
  72. void graph::copy_all_entries() const
  73. { node v;
  74.   forall_nodes(v,*this) copy_node_entry(v->data[0]);
  75.   edge e;
  76.   forall_edges(e,*this) copy_edge_entry(e->data[0]);
  77. }
  78.  
  79. void graph::clear_all_entries() const
  80. { node v;
  81.   forall_nodes(v,*this) clear_node_entry(v->data[0]);
  82.   edge e;
  83.   forall_edges(e,*this) clear_edge_entry(e->data[0]);
  84. }
  85.  
  86.  
  87. graph::graph(const graph& G)  
  88. { node v,w;
  89.   edge e,e1;
  90.   node* node_vec = new node[G.max_n_index+1];
  91.   edge* edge_vec = new edge[G.max_e_index+1];
  92.  
  93.  
  94.   max_n_index = max_e_index = -1;
  95.  
  96.   forall_nodes(v,G) 
  97.     node_vec[v->name] = new_node(v->data[0]);
  98.                              
  99.   forall_edges(e,G) 
  100.    { v = node_vec[e->s->name];
  101.      w = node_vec[e->t->name];
  102.      edge_vec[e->name] = e1 = new edge_struct(v,w,e->data[0]);
  103.      E.append(edge_link(e1));
  104.      e1->name = ++max_e_index;
  105.     }
  106.  
  107.  
  108.   forall_nodes(v,G) 
  109.   { node v1 = node_vec[v->name];
  110.     forall_out_edges(e,v)
  111.        v1->adj_edges[0].append(adj_link1(edge_vec[e->name]));
  112.     forall_in_edges(e,v)
  113.        v1->adj_edges[1].append(adj_link2(edge_vec[e->name]));
  114.    }
  115.  
  116.  
  117.   forall_nodes(v,*this) init_adj_iterator(v); 
  118.  
  119.   parent = G.parent;
  120.   undirected = G.undirected;
  121.  
  122.   delete node_vec;
  123.   delete edge_vec;
  124.  
  125. }
  126.  
  127.  
  128. // subgraph constructors  (do not work for undirected graphs)
  129.  
  130. graph::graph(graph& G, const list<node>& nl, const list<edge>& el)
  131. { // construct subgraph (nl,el) of graph G
  132.  
  133.   parent = &G;
  134.   node v,w;
  135.   edge e;
  136.  
  137.   node* N = new node[G.max_n_index+1];
  138.  
  139.   forall(v,nl)
  140.    { if (graph_of(v) != parent) 
  141.       error_handler(1,"graph: illegal node in subgraph constructor");
  142.      N[v->name] = new_node((GenPtr)v);
  143.     }
  144.  
  145.   forall(e,el)
  146.    { v = source(e);
  147.      w = target(e);
  148.      if ( graph_of(e)!= parent || N[v->name]==0 || N[w->name]==0 ) 
  149.       error_handler(1,"graph: illegal edge in subgraph constructor");
  150.      new_edge(N[v->name],N[w->name],(GenPtr)e);
  151.     }
  152.  
  153.   undirected = G.undirected;
  154.  
  155.   delete N;
  156.  
  157.  }
  158.  
  159. graph::graph(graph& G, const list<edge>& el)
  160. { /* construct subgraph of graph G with edge set el  */
  161.  
  162.   node  v,w;
  163.   edge  e;
  164.   node* N = new node[G.max_n_index+1];
  165.  
  166.   forall_nodes(v,G) N[v->name] = 0;
  167.  
  168.   parent = &G;
  169.  
  170.   forall(e,el)
  171.    { v = source(e);
  172.      w = target(e);
  173.      if (N[v->name] == 0) N[v->name] = new_node((GenPtr)v);
  174.      if (N[w->name] == 0) N[w->name] = new_node((GenPtr)w);
  175.      if ( graph_of(e) != parent )
  176.       error_handler(1,"graph: illegal edge in subgraph constructor");
  177.      new_edge(N[v->name],N[w->name],(GenPtr)e);
  178.     }
  179.  
  180.   undirected = G.undirected;
  181.  
  182.   delete N;
  183.  
  184.  }
  185.  
  186.  
  187. // destructor
  188.  
  189. void graph::clear()
  190. { 
  191.   while ( ! E.empty() ) 
  192.     delete edge(edge_link(E.pop()));
  193.  
  194.   while ( ! V.empty() ) 
  195.   { node v = node(node_link(V.pop()));
  196.     v->adj_edges[0].clear();
  197.     v->adj_edges[1].clear();
  198.     delete v;
  199.    }
  200.  
  201.   max_n_index = max_e_index = -1;
  202. }
  203.  
  204. list<node> graph::all_nodes() const
  205. { list<node> result;
  206.   node v;
  207.   forall_nodes(v,*this) result.append(v);
  208.   return result;
  209. }
  210.  
  211. list<edge> graph::all_edges() const
  212. { list<edge> result;
  213.   edge e;
  214.   forall_edges(e,*this) result.append(e);
  215.   return result;
  216. }
  217.  
  218. list<edge> graph::adj_edges(node v) const
  219. { list<edge> result;
  220.   edge e;
  221.   forall_adj_edges(e,v) result.append(e);
  222.   return result;
  223. }
  224.  
  225.  
  226. list<node> graph::adj_nodes(node v) const
  227. { list<node> result;
  228.   edge e;
  229.   forall_adj_edges(e,v) result.append(target(e));
  230.   return result;
  231. }
  232.  
  233.  
  234.  
  235. void init_node_data(const graph& G,int i, GenPtr x)
  236. { node v;
  237.   forall_nodes(v,G) v->data[i] = x;
  238.  }
  239.